#include <iostream>
using namespace std;

int Partition(int r[], int low, int high){  //划分函数
    int i = low, j = high, pivot=r[low];    // 选第一个元素作为基准元素
    while (i<j)
    {
        while(i<j && r[j] > pivot) j--;      // 从右边往左扫描，直到第一个小于基准元素的值
        if(i < j){
            swap(r[i++], r[j]);   // 将小于基准元素的值与基准元素进行替换
        
        }
        while(i < j && r[i] < pivot) i++;  // 从左往右扫描，知道第一个大于基准元素的值
        if(i < j){
            swap(r[i], r[j--]);    // 将大于基准元素的值与基准元素进行替换
        }
    }
    return i;
}

void QuickSort(int R[], int low, int high){
    int mid;
    if(low < high){
        mid=Partition(R, low, high);
        QuickSort(R, low, mid-1);
        QuickSort(R, mid + 1, high);
    }
}

int main(){
    int a[1000];
    int i,N;
    cout<<"请先输入要排序的数据的个数：";
    cin >> N;
    cout<<"请输入要排序的数据：";
    for ( i = 0; i < N; i++){
        cin >> a[i];
    }
    cout<<endl;
    QuickSort(a, 0, N - 1);
    cout<<"排序后的序列为："<<endl;
    for ( i = 0; i < N; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}
